package mine.code.question.动态规划;

import javafx.beans.binding.DoubleExpression;
import org.junit.Test;

import java.util.Arrays;

/**
 * 我们将给定的数组 A 分成 K 个相邻的非空子数组 ，我们的分数由每个子数组内的平均值的总和构成。计算我们所能得到的最大分数是多少。
 * <p>
 * 注意我们必须使用 A 数组中的每一个数进行分组，并且分数不一定需要是整数。
 * <p>
 * 示例:
 * 输入:
 * A = [9,1,2,3,9]
 * K = 3
 * 输出: 20
 * 解释:
 * A 的最优分组是[9], [1, 2, 3], [9]. 得到的分数是 9 + (1 + 2 + 3) / 3 + 9 = 20.
 * 我们也可以把 A 分成[9, 1], [2], [3, 9].
 * 这样的分组得到的分数为 5 + 2 + 6 = 13, 但不是最大值.
 *
 * @author caijinnan
 * @date 2020/6/9 9:57
 */
public class 最大平均值和的分组 {
    // 9 1 2 3 9

    @Test
    public void run() {
        int[] A = {9, 1, 2, 3, 9};
        System.out.println(largestSumOfAverages(A, 3));
    }

    //dp[i][j] = max(for(dp[index][j-1]+average(index-A.length)))
    public double largestSumOfAverages(int[] A, int K) {
        int length = A.length;
        int[] sum = new int[length + 1];
        for (int i = 0; i < length; i++) {
            sum[i + 1] = sum[i] + A[i];
        }
        double[] dp = new double[length];
        for (int i = 0; i < length; i++) {
            dp[i] = (double) (sum[length] - sum[i]) / (length - i);
        }
        for (int k = 0; k < K - 1; k++) {
            for (int i = 0; i < length; i++) {
                for (int j = i + 1; j < length; j++) {
                    dp[i] = Math.max(dp[i], (double) (sum[j] - sum[i]) / (j - i) + dp[j]);
                }
            }
        }
        System.out.println(Arrays.toString(dp));
        return dp[0];
    }
}